package week3;

import java.util.ArrayDeque;
import java.util.Deque;

public class test1 {
    public static void main(String[] args) {
        int[] nums={3,2,3,1,2,4,5,5,6};
        int k=4;

        //方法一:递减排序第k个就是第k大的元素
       bubbleSort(nums);
        for (int i = 0; i < nums.length-1; i++) {
           if (i==k-1){
              System.out.println(nums[i]);
           }
        }

        //方法二:使用压缩栈  这里直接使用Java定义好的Deque类作为栈
        Deque<Integer> stack=stackSort(nums);
        System.out.println(stack);
        for (int i = 0; i <k-1 ; i++) {
            stack.pop();
        }
        System.out.println(stack.peek());

    }
    //冒泡排序
    public static void bubbleSort(int[] arr) {
        if (arr == null || arr.length <= 1) return;
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            boolean swap = false;

            for (int j = 0; j < n - 1 - i; j++) {
                if (arr[j] < arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swap = true;
                }
            }
            if (!swap) break;
        }
    }

    //压缩栈排序
    public static Deque<Integer> stackSort(int[] arr) {
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i :arr){
            stack.push(i);
        }
        Deque<Integer> temp = new ArrayDeque<>();
        while (!stack.isEmpty()){
            int current = stack.pop();
            while (!temp.isEmpty() && temp.peek() > current){
                stack.push(temp.pop());
            }
            temp.push(current);
        }
        return temp;
    }


}
